home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / viewers / giflib12 / lib / quantize.c < prev   
Encoding:
C/C++ Source or Header  |  1991-06-15  |  12.8 KB  |  336 lines
  1. /*****************************************************************************
  2. *   "Gif-Lib" - Yet another gif library.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber            IBM PC Ver 0.1,    Jun. 1989    *
  5. ******************************************************************************
  6. * Module to quatize high resolution image into lower one. You may want to    *
  7. * peek into the following article this code is based on:             *
  8. * "Color Image Quantization for frame buffer Display", by Paul Heckbert      *
  9. * SIGGRAPH 1982 page 297-307.                             *
  10. ******************************************************************************
  11. * History:                                     *
  12. * 5 Jan 90 - Version 1.0 by Gershon Elber.                     *
  13. *****************************************************************************/
  14.  
  15. #ifdef __MSDOS__
  16. #include <dos.h>
  17. #include <alloc.h>
  18. #include <stdlib.h>
  19. #include <graphics.h>
  20. #endif /* __MSDOS__ */
  21.  
  22. #include <stdio.h>
  23. #include "gif_lib.h"
  24.  
  25. #define PROGRAM_NAME    "GIF_LIBRARY"
  26.  
  27. #define ABS(x)    ((x) > 0 ? (x) : (-(x)))
  28.  
  29. /* The colors are stripped to 5 bits per primary color if non MSDOS system  */
  30. /* or to 4 (not enough memory...) if MSDOS as first step.            */
  31. #ifdef __MSDOS__
  32. #define COLOR_ARRAY_SIZE 4096
  33. #define BITS_PER_PRIM_COLOR 4
  34. #define MAX_PRIM_COLOR      0x0f
  35. #else
  36. #define COLOR_ARRAY_SIZE 32768
  37. #define BITS_PER_PRIM_COLOR 5
  38. #define MAX_PRIM_COLOR      0x1f
  39. #endif /* __MSDOS__ */
  40.  
  41. extern int _GifError;
  42.  
  43. #ifdef SYSV
  44. static char *VersionStr =
  45.         "Gif library module,\t\tGershon Elber\n\
  46.     (C) Copyright 1989 Gershon Elber, Non commercial use only.\n";
  47. #else
  48. static char *VersionStr =
  49.     PROGRAM_NAME
  50.     "    IBMPC "
  51.     GIF_LIB_VERSION
  52.     "    Gershon Elber,    "
  53.     __DATE__ ",   " __TIME__ "\n"
  54.     "(C) Copyright 1989 Gershon Elber, Non commercial use only.\n";
  55. #endif /* SYSV */
  56.  
  57. static int SortRGBAxis;
  58.  
  59. typedef struct QuantizedColorType {
  60.     GifByteType RGB[3];
  61.     GifByteType NewColorIndex;
  62.     long Count;
  63.     struct QuantizedColorType *Pnext;
  64. } QuantizedColorType;
  65.  
  66. typedef struct NewColorMapType {
  67.     GifByteType RGBMin[3], RGBWidth[3];
  68.     unsigned int NumEntries;/* # of QuantizedColorType in linked list below. */
  69.     long Count;               /* Total number of pixels in all the entries. */
  70.     QuantizedColorType *QuantizedColors;
  71. } NewColorMapType;
  72.  
  73. static int SubdivColorMap(NewColorMapType *NewColorSubdiv,
  74.               unsigned int ColorMapSize,
  75.               unsigned int *NewColorMapSize);
  76. #ifdef __MSDOS__
  77. static int SortCmpRtn(const VoidPtr Entry1, const VoidPtr Entry2);
  78. #else
  79. static int SortCmpRtn(VoidPtr Entry1, VoidPtr Entry2);
  80. #endif /* __MSDOS__ */
  81.  
  82. /******************************************************************************
  83. * Quantize high resolution image into lower one. Input image consists of a    *
  84. * 2D array for each of the RGB colors with size Width by Height. There is no  *
  85. * Color map for the input. Output is a quantized image with 2D array of       *
  86. * indexes into the output color map.                          *
  87. *   Note input image can be 24 bits at the most (8 for red/green/blue) and    *
  88. * the output has 256 colors at the most (256 entries in the color map.).      *
  89. * ColorMapSize specifies size of color map up to 256 and will be updated to   *
  90. * real size before returning.                              *
  91. *   Also non of the parameter are allocated by this routine.              *
  92. *   This function returns GIF_OK if succesfull, GIF_ERROR otherwise.          *
  93. ******************************************************************************/
  94. int QuantizeBuffer(unsigned int Width, unsigned int Height, int *ColorMapSize,
  95.     GifByteType *RedInput, GifByteType *GreenInput, GifByteType *BlueInput,
  96.     GifByteType *OutputBuffer, GifColorType *OutputColorMap)
  97. {
  98.     unsigned int i, j, Index, NewColorMapSize, NumOfEntries, MaxRGBError[3];
  99.     long Red, Green, Blue;
  100.     NewColorMapType NewColorSubdiv[256];
  101.     QuantizedColorType *ColorArrayEntries, *QuantizedColor;
  102.  
  103.     if ((ColorArrayEntries = (QuantizedColorType *)
  104.         malloc(sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE)) == NULL) {
  105.     _GifError = E_GIF_ERR_NOT_ENOUGH_MEM;
  106.     return GIF_ERROR;
  107.     }
  108.  
  109.     for (i = 0; i < COLOR_ARRAY_SIZE; i++) {
  110.     ColorArrayEntries[i].RGB[0]= i >> (2 * BITS_PER_PRIM_COLOR);
  111.     ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) &
  112.                                 MAX_PRIM_COLOR;
  113.     ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR;
  114.     ColorArrayEntries[i].Count = 0;
  115.     }
  116.  
  117.     /* Sample the colors and their distribution: */
  118.     for (i = 0; i < Width * Height; i++) {
  119.     Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR))
  120.             << (2 * BITS_PER_PRIM_COLOR)) +
  121.         ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR))
  122.             << BITS_PER_PRIM_COLOR) +
  123.         (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR));
  124.     ColorArrayEntries[Index].Count++;
  125.     }
  126.  
  127.     /* Put all the colors in the first entry of the color map, and call the  */
  128.     /* recursive subdivision process.                         */
  129.     for (i = 0; i < 256; i++) {
  130.     NewColorSubdiv[i].QuantizedColors = NULL;
  131.     NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0;
  132.     for (j = 0; j < 3; j++) {
  133.         NewColorSubdiv[i].RGBMin[j] = 0;
  134.         NewColorSubdiv[i].RGBWidth[j] = 255;
  135.     }
  136.     }
  137.  
  138.     /* Find the non empty entries in the color table and chain them: */
  139.     for (i = 0; i < COLOR_ARRAY_SIZE; i++)
  140.     if (ColorArrayEntries[i].Count > 0) break;
  141.     QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i];
  142.     NumOfEntries = 1;
  143.     while (++i < COLOR_ARRAY_SIZE)
  144.     if (ColorArrayEntries[i].Count > 0) {
  145.         QuantizedColor -> Pnext = &ColorArrayEntries[i];
  146.         QuantizedColor = &ColorArrayEntries[i];
  147.         NumOfEntries++;
  148.     }
  149.     QuantizedColor -> Pnext = NULL;
  150.  
  151.     NewColorSubdiv[0].NumEntries = NumOfEntries;/* Different sampled colors. */
  152.     NewColorSubdiv[0].Count = ((long) Width) * Height;            /* Pixels. */
  153.     NewColorMapSize = 1;
  154.     if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &NewColorMapSize) !=
  155.                                      GIF_OK) {
  156.     free((char *) ColorArrayEntries);
  157.     return GIF_ERROR;
  158.     }
  159.     if (NewColorMapSize < *ColorMapSize) {
  160.     /* And clear rest of color map: */
  161.     for (i = NewColorMapSize; i < *ColorMapSize; i++)
  162.         OutputColorMap[i].Red =
  163.         OutputColorMap[i].Green =
  164.         OutputColorMap[i].Blue = 0;
  165.     }
  166.  
  167.     /* Average the colors in each entry to be the color to be used in the    */
  168.     /* output color map, and plug it into the output color map itself.       */
  169.     for (i = 0; i < NewColorMapSize; i++) {
  170.     if ((j = NewColorSubdiv[i].NumEntries) > 0) {
  171.         QuantizedColor = NewColorSubdiv[i].QuantizedColors;
  172.         Red = Green = Blue = 0;
  173.         while (QuantizedColor) {
  174.         QuantizedColor -> NewColorIndex = i;
  175.         Red += QuantizedColor -> RGB[0];
  176.         Green += QuantizedColor -> RGB[1];
  177.         Blue += QuantizedColor -> RGB[2];
  178.         QuantizedColor = QuantizedColor -> Pnext;
  179.         }
  180.         OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j;
  181.         OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j;
  182.         OutputColorMap[i].Blue= (Blue << (8 - BITS_PER_PRIM_COLOR)) / j;
  183.     }
  184.     else
  185.         GIF_MESSAGE("Null entry in quantized color map - thats weird.");
  186.     }
  187.  
  188.     /* Finally scan the input buffer again and put the mapped index in the   */
  189.     /* output buffer.                                 */
  190.     MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0;
  191.     for (i = 0; i < Width * Height; i++) {
  192.     Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR))
  193.             << (2 * BITS_PER_PRIM_COLOR)) +
  194.         ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR))
  195.             << BITS_PER_PRIM_COLOR) +
  196.         (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR));
  197.     Index = ColorArrayEntries[Index].NewColorIndex;
  198.     OutputBuffer[i] = Index;
  199.     if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i]))
  200.         MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]);
  201.     if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i]))
  202.         MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]);
  203.     if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i]))
  204.         MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]);
  205.     }
  206.  
  207. #ifdef DEBUG
  208.     fprintf(stderr,
  209.         "Quantization L(0) errors: Red = %d, Green = %d, Blue = %d.\n",
  210.                 MaxRGBError[0], MaxRGBError[1], MaxRGBError[2]);
  211. #endif /* DEBUG */
  212.  
  213.     free((char *) ColorArrayEntries);
  214.  
  215.     *ColorMapSize = NewColorMapSize;
  216.  
  217.     return GIF_OK;
  218. }
  219.  
  220. /******************************************************************************
  221. * Routine to subdivide the RGB space recursively using median cut in each     *
  222. * axes alternatingly until ColorMapSize different cubes exists.              *
  223. * The biggest cube in one dimension is subdivide unless it has only one entry.*
  224. * Returns GIF_ERROR if failed, otherwise GIF_OK.                  *
  225. ******************************************************************************/
  226. static int SubdivColorMap(NewColorMapType *NewColorSubdiv,
  227.               unsigned int ColorMapSize,
  228.               unsigned int *NewColorMapSize)
  229. {
  230.     int MaxSize;
  231.     unsigned int i, j, Index = 0, NumEntries, MinColor, MaxColor;
  232.     long Sum, Count;
  233.     QuantizedColorType *QuantizedColor, **SortArray;
  234.  
  235.     while (ColorMapSize > *NewColorMapSize) {
  236.     /* Find candidate for subdivision: */
  237.     MaxSize = -1;
  238.     for (i = 0; i < *NewColorMapSize; i++) {
  239.         for (j = 0; j < 3; j++) {
  240.         if (((int) NewColorSubdiv[i].RGBWidth[j]) > MaxSize &&
  241.             NewColorSubdiv[i].NumEntries > 1) {
  242.             MaxSize = NewColorSubdiv[i].RGBWidth[j];
  243.             Index = i;
  244.             SortRGBAxis = j;
  245.         }
  246.         }
  247.     }
  248.  
  249.     if (MaxSize == -1)
  250.         return GIF_OK;
  251.  
  252.     /* Split the entry Index into two along the axis SortRGBAxis: */
  253.  
  254.     /* Sort all elements in that entry along the given axis and split at */
  255.     /* the median.                                 */
  256.     if ((SortArray = (QuantizedColorType **)
  257.         malloc(sizeof(QuantizedColorType *) *
  258.            NewColorSubdiv[Index].NumEntries)) == NULL)
  259.             return GIF_ERROR;
  260.     for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors;
  261.          j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL;
  262.          j++, QuantizedColor = QuantizedColor -> Pnext)
  263.         SortArray[j] = QuantizedColor;
  264.     qsort(SortArray, NewColorSubdiv[Index].NumEntries,
  265.           sizeof(QuantizedColorType *), SortCmpRtn);
  266.  
  267.     /* Relink the sorted list into one: */
  268.     for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++)
  269.         SortArray[j] -> Pnext = SortArray[j + 1];
  270.     SortArray[NewColorSubdiv[Index].NumEntries - 1] -> Pnext = NULL;
  271.     NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0];
  272.     free((char *) SortArray);
  273.  
  274.     /* Now simply add the Counts until we have half of the Count: */
  275.     Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor -> Count;
  276.     NumEntries = 1;
  277.     Count = QuantizedColor -> Count;
  278.     while ((Sum -= QuantizedColor -> Pnext -> Count) >= 0 &&
  279.            QuantizedColor -> Pnext != NULL &&
  280.            QuantizedColor -> Pnext -> Pnext != NULL) {
  281.         QuantizedColor = QuantizedColor -> Pnext;
  282.         NumEntries++;
  283.         Count += QuantizedColor -> Count;
  284.     }
  285.     /* Save the values of the last color of the first half, and first    */
  286.     /* of the second half so we can update the Bounding Boxes later.     */
  287.     /* Also as the colors are quantized and the BBoxes are full 0..255,  */
  288.     /* they need to be rescaled.                         */
  289.     MaxColor = QuantizedColor -> RGB[SortRGBAxis];/* Max. of first half. */
  290.     MinColor = QuantizedColor -> Pnext -> RGB[SortRGBAxis];/* of second. */
  291.     MaxColor <<= (8 - BITS_PER_PRIM_COLOR);
  292.     MinColor <<= (8 - BITS_PER_PRIM_COLOR);
  293.  
  294.     /* Partition right here: */
  295.     NewColorSubdiv[*NewColorMapSize].QuantizedColors =
  296.         QuantizedColor -> Pnext;
  297.     QuantizedColor -> Pnext = NULL;
  298.     NewColorSubdiv[*NewColorMapSize].Count = Count;
  299.     NewColorSubdiv[Index].Count -= Count;
  300.     NewColorSubdiv[*NewColorMapSize].NumEntries =
  301.         NewColorSubdiv[Index].NumEntries - NumEntries;
  302.     NewColorSubdiv[Index].NumEntries = NumEntries;
  303.     for (j = 0; j < 3; j++) {
  304.         NewColorSubdiv[*NewColorMapSize].RGBMin[j] =
  305.         NewColorSubdiv[Index].RGBMin[j];
  306.         NewColorSubdiv[*NewColorMapSize].RGBWidth[j] =
  307.         NewColorSubdiv[Index].RGBWidth[j];
  308.     }
  309.     NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] =
  310.         NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] +
  311.         NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] -
  312.         MinColor;
  313.     NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor;
  314.  
  315.     NewColorSubdiv[Index].RGBWidth[SortRGBAxis] =
  316.         MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis];
  317.  
  318.     (*NewColorMapSize)++;
  319.     }
  320.  
  321.     return GIF_OK;
  322. }
  323.  
  324. /******************************************************************************
  325. * Routine called by qsort to compare to entries.                  *
  326. ******************************************************************************/
  327. #ifdef __MSDOS__
  328. static int SortCmpRtn(const VoidPtr Entry1, const VoidPtr Entry2)
  329. #else
  330. static int SortCmpRtn(VoidPtr Entry1, VoidPtr Entry2)
  331. #endif /* __MSDOS__ */
  332. {
  333.     return (* ((QuantizedColorType **) Entry1)) -> RGB[SortRGBAxis] -
  334.        (* ((QuantizedColorType **) Entry2)) -> RGB[SortRGBAxis];
  335. }
  336.